//树的子结构: https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
  public:
    bool IsSameFromBegin(TreeNode* begin, TreeNode* beginSub) {
//和下面的寻找代码不同的是，现在要执行的是第二步
        if (nullptr == beginSub) 
		{ 
			//beginSub为nullptr，说明已经比较完了
            return true;
        }
        if (nullptr == begin) 
		{ 
			//begin为空，说明beginSub不是你的子树
            return false;
        }
        if (begin->val != beginSub->val) 
		{
            return false; //说明，整树中，有不相等的节点
        }
		//在比较左右子树是否相等
		//这里大家深度想想递归是怎么返回的【整个递归的结果，由最深层调用的结果决定】
        return IsSameFromBegin(begin->left, beginSub->left) && IsSameFromBegin(begin -> right, beginSub->right);
    }

	//比较的过程要分为两步
	//1. 先确定起始位置
	//2. 在确定从该位置开始，后续的左右子树的内容是否一致
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) 
	{
		//下面逻辑整体执行的是第一步
		//先判定两棵树有没有为空的情况
        if (pRoot1 == nullptr || pRoot2 == nullptr) 
		{
            return false;
        }

        bool result = false;
		//找到了起始位置
        if (pRoot1->val == pRoot2->val) 
		{
			//从该起始位置开始，查找是否一致
            result = IsSameFromBegin(pRoot1, pRoot2);
        }

		//如果pRoot1->val ！= pRoot2->val or 从起始位置开始，不一致
        if (!result) 
		{
			//在A树的左子树使用相同的方式找找
            result = HasSubtree(pRoot1->left, pRoot2);
        }

		//左子树没有，再在右子树找找
        if (!result) 
		{
            result = HasSubtree(pRoot1->right, pRoot2);
        }
        return result;
    }
};